package main.Q101_200;

import java.util.*;

public class Q141_150 {
    public static void main(String[] args) {
        System.out.println("Question141：环形链表");
        System.out.println("Question142：环形链表Ⅱ");
        System.out.println("Question143：重排链表");
        System.out.println("Question144：二叉树的前序遍历");
        System.out.println("Question145：二叉树的后序遍历");
        System.out.println("Question146：LRU 缓存");
        System.out.println("Question147：对链表进行插入排序");
        System.out.println("Question148：排序链表");
        System.out.println("Question149：直线上最多的点数");
        System.out.println("Question150：逆波兰表达式求值");
    }
}

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
      val = x;
      next = null;
  }
}

class Question141{
    public boolean hasCycle(ListNode head) {
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow) {
                return true;
            }
        }
        return false;
    }
//    public boolean hasCycle(ListNode head) {
//        Map<String,Integer> map=new HashMap<>();
//        int pos=0,i=0;
//        boolean flag=false;
//        while (head!=null){
//            if (map.containsKey(head.toString())){//出现环
//                flag=true;
//                break;
//            }else {//未出现环，将该节点存入
//                map.put(head.toString(),i++);
//                head=head.next;
//            }
//        }
//        return flag;
//    }
}

class Question142{
    public ListNode detectCycle(ListNode head) {
        if (head==null||head.next==null) return null;
        ListNode slow=head,fast=head;
        do {
            if (fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }else return null;
        }while (fast!=slow);//判断存在环
        if (fast!=null) {//填补快慢指针步差
            slow = head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
        }
        return fast;
    }
}

class Question143{
    public void reorderList(ListNode head) {
        ListNode curHead=head;
        List<ListNode> list=new ArrayList<>();
        while (curHead!=null){
            list.add(curHead);
            curHead=curHead.next;
        }
        List<ListNode> reverseList=new ArrayList<>(list);
        Collections.reverse(reverseList);
        int count=1,index=1,reverseIndex=0;
        curHead=head;
        while (count<list.size()){
            curHead.next= reverseList.get(reverseIndex);
            count++;
            reverseIndex++;
            curHead=curHead.next;
            curHead.next=list.get(index);
            count++;
            index++;
            curHead=curHead.next;
        }
        curHead.next=null;
    }
}

class Question144{
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        process(root,list);
        return list;
    }
    public void process(TreeNode node,List<Integer> list){
        if (node==null){
            return;
        }
        list.add(node.val);
        process(node.left,list);
        process(node.right,list);
    }
}

class Question145{
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        process(root,list);
        return list;
    }
    public void process(TreeNode node,List<Integer> list){
        if (node==null){
            return;
        }
        process(node.left,list);
        process(node.right,list);
        list.add(node.val);
    }
}

class Question146{
    public HashMap<Integer,Integer> hashMap=new HashMap<>();
    public Deque<Info> infos1=new ArrayDeque<>();
    public HashMap<Integer,Info> hashMap1=new HashMap<>();
    public int capacity;
    public static class Info{
        int key;
        int time;
        public Info(int key, int time) {
            this.key = key;
            this.time = time;
        }
    }
    public Question146(int capacity) {
        this.capacity=capacity;
    }
    public int get(int key) {
        if (hashMap.containsKey(key)){
            Integer integer = hashMap.get(key);
            Info info = hashMap1.get(key);
            infos1.remove(info);
            info.time= Math.toIntExact(System.currentTimeMillis()>>11);
            infos1.addLast(info);
            return integer;
        }else {
            return -1;
        }
    }
    public void put(int key, int value) {
        if (hashMap.size()==capacity&&!hashMap.containsKey(key)){
            Info poll = infos1.pollFirst();
            hashMap.remove(poll.key);
            hashMap1.remove(poll.key);
            Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
            hashMap1.put(key,info);
            hashMap.put(key,value);
            infos1.addLast(info);
        }else {
            if (hashMap.containsKey(key)){
                hashMap.put(key,value);
                Info info = hashMap1.get(key);
                infos1.remove(info);
                info.time= (int) System.currentTimeMillis()>>11;
                infos1.addLast(info);
            }else {
                Info info = new Info(key, Math.toIntExact(System.currentTimeMillis()>>11));
                hashMap1.put(key,info);
                hashMap.put(key,value);
                infos1.addLast(info);
            }
        }
    }
}

class Question147{
    public ListNode insertionSortList(ListNode head) {
        List<Integer> list=new ArrayList<>();
        ListNode vir=head;
        while (vir !=null) {
            list.add(vir.val);
            vir=vir.next;
        }
        Collections.sort(list);
        vir=head;
        for (Integer num:list) {
            vir.val=num;
            vir=vir.next;
        }
        return head;
    }
}

class Question148{
    public ListNode sortList(ListNode head) {
        ListNode now=head;
        List<Integer> list=new ArrayList<>();
        while (now!=null){
            list.add(now.val);
            now=now.next;
        }
        Integer[] arr=list.toArray(new Integer[0]);
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        now=head;
        for (int i=0;i< arr.length;i++){
            now.val=arr[i];
            now=now.next;
        }
        return head;
    }
}

class Question149{
    public int maxPoints(int[][] points) {
        if (points.length<3) return points.length;
        int max=0;
        int f=points.length>>1;
        for (int i=0;i<points.length;i++){
            int[] m=points[i];
            for (int j=i+1;j<points.length;j++){//两点确定一条直线
                int tempMax=2;
                int dx=points[j][0]-m[0],dy=points[j][1]-m[1],d=dx*m[1]-dy*m[0];
                for (int k=j+1;k<points.length;k++){
                    if (dx*points[k][1]==dy*points[k][0]+d) tempMax++;
                }
                if (tempMax>f) return tempMax;
                max=Math.max(max,tempMax);
            }
        }
        return max;
    }
}

class Question150{
    public int evalRPN(String[] tokens) {
        int result=0;
        String last,pre;
        Stack<String> stack=new Stack<>();
        for (int i=0;i< tokens.length;i++){
            switch (tokens[i]){//遇到运算符时，栈中弹出2个元素进行运算，并将结果压回栈中
                case "+":
                    last=stack.pop();//算式的后者
                    pre=stack.pop();//算式的前者
                    result=Integer.valueOf(pre)+Integer.valueOf(last);
                    stack.add(String.valueOf(result));
                    break;
                case "-":
                    last=stack.pop();//算式的后者
                    pre=stack.pop();//算式的前者
                    result=Integer.valueOf(pre)-Integer.valueOf(last);
                    stack.add(String.valueOf(result));
                    break;
                case "*":
                    last=stack.pop();//算式的后者
                    pre=stack.pop();//算式的前者
                    result=Integer.valueOf(pre)*Integer.valueOf(last);
                    stack.add(String.valueOf(result));
                    break;
                case "/":
                    last=stack.pop();//算式的后者
                    pre=stack.pop();//算式的前者
                    result=Integer.valueOf(pre)/Integer.valueOf(last);
                    stack.add(String.valueOf(result));
                    break;
                default:stack.add(tokens[i]);break;
            }
        }
        if (tokens.length==1) result=Integer.valueOf(tokens[0]);
        return result;
    }
}